 1.动态规划之概述
   
   动态规划，简称为DP。
   动态规划是求解最优化问题的一种常用策略。
   动态规划使用步骤
       递归（自顶向下，出现了重叠子问题）
       记忆化（自顶向下,备忘录）
       递推（自底向上，循环）
   1).重要概念
   Dynamic Programming is a method for solving a complex problem by breaking it down into a
collection of simpler subproblems, solving each of those subproblems just once, and storing
their solutions.
   --维基百科
   中文翻译：
       (1).将复杂的原问题拆解成若干个简单的子问题
	   (2).每个子问题仅仅解决1次，并保存它们的解
	   (3).最后推导出原问题的解
   动态规划策略可以解决哪些问题？
   这类问题通常具有两个特点
       最优化问题(最优子结构问题)：通过求解子问题的最优解，可以获得原问题的最优解
       无后效性
   补充：无后效性是指某阶段的状态一旦确定后，后续状态的演变不再受此前各状态及决策的影响(未来与过去无
关)；在推导后面阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态是怎么一步步推导出！！
   无后效性
   从起点(0, 0)走到终点(4, 4)一共有多少种走法？只能向右、向下走
   假设 dp(i, j) 是从(0, 0)走到（i, j）的走法   
       dp(i, 0) = dp(0, j) = 1
       dp(i, j) = dp(i, j – 1) + dp(i – 1, j)
   总结
   推导 dp(i, j) 时只需要用到 dp(i, j – 1)、dp(i – 1, j) 的值 不需要关心 dp(i, j – 1)、dp(i – 1, j) 的值是怎么求出来的
   有后效性
   规则：可以向左、向右、向上、向下走，并且同一个格子不能走 2 次
   有后效性：
       dp(i, j) 下一步要怎么走，还要关心上一步是怎么来的
       还需要考虑 dp(i, j – 1)、dp(i – 1, j) 是怎么来的

 2.使用步骤
  
   定义状态
   状态指的是原问题，子问题的解，例如dp(i)
   设定初始状态
   问题的边界，比如设置dp(0)的值
   确定状态转移方程
   确定 dp(i) 和 dp(i – 1) 的关系
 
 3.案例一
   
   leetcode_322_零钱兑换：https://leetcode-cn.com/problems/coin-change/
   假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？
   此前贪心策略求解结果是5枚硬币，并非是最优解！！
   思路：
       定义状态
       dp(n):凑到 n 分需要的最少硬币个数
       设定初始状态
       dp(25)=dp(20)=dp(5)=dp(1)=1
       确定状态转移方程
           如果第 1 次选择了 25 分的硬币，那么 dp(n) = dp(n – 25) + 1
           如果第 1 次选择了 20 分的硬币，那么 dp(n) = dp(n – 20) + 1
           如果第 1 次选择了 5 分的硬币，那么 dp(n) = dp(n – 5) + 1
           如果第 1 次选择了 1 分的硬币，那么 dp(n) = dp(n – 1) + 1
           所以 dp(n) = min { dp(n – 25), dp(n – 20), dp(n – 5), dp(n – 1) } + 1
   代码实现
package com.lg.dp;

/**
 * 使用动态规划求解最少硬币个数
 */
public class CoinsDemo {
    //1.定义一个状态，方法,凑够n分的最少硬币个数
    //dp(n):凑到 n 分需要的最少硬币个数
    static int coinChange(int n) {
        //递归基
        if (n < 1){return Integer.MAX_VALUE;}
        //2 确定初始状态
        if (n == 1 || n == 5 || n == 20 || n == 25) {
            return 1;
        }
        //3.确定状态转移方程:dp(n)与dp(n-1)的关系，
        /**
         * 如果第一次选择了1分；coinChange(n)=coinChange(n-1)+1
         * 如果第一次选择了5分；coinChange(n)=coinChange(n-5)+1
         * 如果第一次选择了20分；coinChange(n)=coinChange(n-20)+1
         * 如果第一次选择了25分；coinChange(n)=coinChange(n-25)+1
         * 以上四种情况选择哪一种呢？应该选择的是硬币个数最少的这种
         */
        final int min1 = Math.min(coinChange(n - 1), coinChange(n - 5));
        final int min2 = Math.min(coinChange(n - 20), coinChange(n - 25));
        return Math.min(min1, min2)+1;
    }

    public static void main(String[] args) {
        System.out.println(coinChange(41));
    }
}

   这种递归方式会存在大量重复计算，时间复杂度是比较高的！！
   1).优化一
   使用数组保存计算过的子问题的解，避免重复计算！！
   代码实现 
package com.lg.dp;

/**
 * 使用动态规划求解最少硬币个数,使用备忘录方式:记忆搜索
 * 大体思路
 * 把计算过的结果记录下来，每个子问题的解仅仅解决一次，
 * 使用数组报错子问题的解
 */
public class CoinsDemo2 {
    /**
     * 定义找零钱方法
     */
    static int coins(int n) {
        //过滤不合理的值
        if (n<1) {return 1;}
        //定义一个数组保存子问题的解，dp(n)...dp(2),dp(1)
        int[] dp=new int[n+1]; //数组索引从0开始，只是为了与dp(n)位置对应
        //初始状态准备好
        dp[1]=dp[5]=dp[20]=dp[1]=1;
        return coins(n, dp); //调用coins(n, dp)
    }

    static int coins(int n, int[] dp) {
        //缺少递归基
        if (n < 1){return Integer.MAX_VALUE;}
        /**
         * 子问题的解保存在dp数组中，如果已经计算过则直接取出
         * 否则需要计算，并保存到dp数组中
         */
        if (dp[n]==0) {
            //说明dp(n)没有被计算，需要计算
            int min1 = Math.min(coins(n - 1, dp), coins(n - 5, dp));
            int min2 = Math.min(coins(n - 20, dp), coins(n - 25, dp));
            dp[n]=Math.min(min1, min2)+1;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(coins(41));
    }
}

   2).优化二
   使用递推方式实现，从小计算到大。
   代码实现
package com.lg.dp;

/**
 * 使用动态规划求解最少硬币个数,使用递推方式，由小到大
 * 大体思路
 *  从小计算到到，dp(1),dp(2)...dp(n)
 */
public class CoinsDemo3 {
    /**
     * 递推方式实现找零钱-动态规划版本
     */
    static int coins(int n){ //对应dp(n)
        //过滤不合理的值
        if (n <1) {
            //说明钱数不合理
            return -1;
        }
        //使用一个数组盛放子问题的解
        int[] dp=new int[n+1];
        //从小问题计算直到计算大问题的解

        for (int i = 1; i <=n; i++) {
            int min=Integer.MAX_VALUE;
            min=Math.min(min, dp[i-1]);
            if (i >= 5) min=Math.min(min, dp[i-5]);
            if (i >= 20) min=Math.min(min, dp[i-20]);
            if (i >= 25) min=Math.min(min, dp[i-25]);
            dp[i]=min+1;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(coins(41));
    }
}
   打印硬币的面值
   代码实现
package com.lg.dp;

/**
 * 使用动态规划求解最少硬币个数,使用递推方式，由小到大
 * 大体思路
 *  从小计算到到，dp(1),dp(2)...dp(n)
 */
public class CoinsDemo3 {
    public static void main(String[] args) {
        System.out.println(coins(6));
    }
    /**
     * 递推方式实现找零钱-动态规划版本
     */
    static int coins(int n){ //对应dp(n)
        //过滤不合理的值
        if (n <1) {
            //说明钱数不合理
            return -1;
        }
        //使用一个数组盛放子问题的解
        int[] dp=new int[n+1];
        //准备一个数组记录下选择了那些面值
        int[] selected= new int[dp.length];
        //从小问题计算直到计算大问题的解
        for (int i = 1; i <=n; i++) {
//            int min=Integer.MAX_VALUE;
//            min=Math.min(min, dp[i-1]);
            int min= dp[i-1]; //当前i分选择硬币的最后一枚面值大小
            selected[i] =1;
            if (i >= 5 && dp[i-5] < min) {
                min=dp[i-5];
                selected[i]=5;
            }
            if (i >= 20 && dp[i-20] < min) {
                min=dp[i-20];
                selected[i]=20;
            }
            if (i >= 25 && dp[i-25] < min) {
                min=dp[i-25];
                selected[i]=25;
            }
            dp[i]=min+1;
        }
        printSelected(selected, n);
        return dp[n];
    }

    //打印selected数组的面值信息
    static void printSelected(int[] selected, int n) {
        while (n >0){
//            selected[n] //第一枚硬币，下一枚硬币的索引是当前索引减去取出的面值
            System.out.print(selected[n] + "_");
            n-=selected[n];
        }
        System.out.println();
    }

}
   
   通用方案
   代码实现      
package com.lg.dp;

/**
 * 使用通用方案，接收金额，面值
 * 大体思路
 * 从小计算到到，dp(1),dp(2)...dp(n)
 */
public class CoinsDemo4 {
    public static void main(String[] args) {

        System.out.println(coinChange(new int[]{5, 20, 25}, 20));
    }

    /**
     * 力扣通用版本
     */
    static int coinChange(int[] coins, int amount) {
        //过滤不合理的值
        if (amount < 1 || coins == null || coins.length == 0) return 0;
        //使用递推方式
        int[] dp = new int[amount + 1];
        //遍历钱
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            //遍历面值
            for (int face : coins) {
                //需要比较i与面值的大小关系
                if (i < face || dp[i-face] < 0) {
                    continue;
                }
                min= Math.min(dp[i - face], min);
            }
            if (min==Integer.MAX_VALUE) {
                //面值不符
                dp[i]=-1;
            } else {
                dp[i] = min + 1;
            }
        }
        return dp[amount];
    }
}
 
 